#
# N ,V = map(int,input().split())             # N 个物品的数量 和 V背包容量。
# w,v = map(int,input().split())          # 第 2∼N+1 行包含 2 个正整数 w,v，表示物品的体积和价值。
#
# dp = [0] * (V + 1)          # 初始化动态规划数组
# for i in range(1,N+1):
#     for j in range(1,V+1):
#         if j < i:
#             dp[i][j] = dp[i-1][j]
#         else:
#             data1 = dp[i-1][j]
#             data2 = dp[i-1][j-i]+dp[i][j]
#             dp[i][j] = max(data1,data2)


# # 读取物品数量 N 和背包容量 V
# N, V = map(int, input().split())
#
# # 初始化物品的体积和价值列表
# w = []
# v = []
# # 读取每个物品的体积和价值
# for _ in range(N):
#     volume, value = map(int, input().split())
#     w.append(value)
#     v.append(volume)
#
# # 初始化动态规划二维数组
# dp = [[0] * (V + 1) for _ in range(N + 1)]
#
# # 动态规划过程
# for i in range(1, N + 1):
#     for j in range(1, V + 1):
#         if j < v[i - 1]:
#             # 当前背包容量不足以放入第 i 个物品
#             dp[i][j] = dp[i - 1][j]
#         else:
#             # 选择放入或不放入第 i 个物品的最大值
#             data1 = dp[i - 1][j]
#             data2 = dp[i - 1][j - v[i - 1]] + w[i - 1]
#             dp[i][j] = max(data1, data2)
#
# # 输出最大价值
# print(dp[N][V])








# 定义一个物品体积和一个价值的列表
num_v = []
num_w = []
# 输入物品数量 N 和背包容量 M
N, M = map(int, input().split())
# 遍历每个物品的体积和价值
for i in range(N):
    v, w = map(int, input().split())
    num_v.append(v)                 # 将当前物品的体积 v 添加到 num_v 列表中
    num_w.append(w)                 # 将当前物品的价值 w 添加到 num_w 列表中
""" 创建一个二维列表 dp 用于动态规划
    dp[i][j] 为前 i 个物品在背包容量为 j 时能获得的最大价值
    列表的行数为 N + 1，列数为 M + 1，初始值都为 0
    这里多创建一行一列是为了方便处理边界情况，例如没有物品（i = 0）或背包容量为 0（j = 0）时         """
dp = [[0] * (M + 1) for i in range(N + 1)]
# 开始填充 dp 数组，外层循环遍历每个物品
for i in range(1, N + 1):
    for j in range(1, M + 1):       # 遍历从背包容量 j 从 1 ~ M
        if j < num_v[i - 1]:        # 判断当前背包容量 j 是否小于第 i 个物品的体积 num_v[i - 1]
            # 如果当前背包容量不足以放入第 i 个物品
            # 那前 i 个物品在背包容量为 j 时能获得的最大价值就等于前 i - 1 个物品在相同容量下的最大价值
            dp[i][j] = dp[i - 1][j]
        else:
            # 不放入第 i 个物品时的最大价值，即前 i - 1 个物品在背包容量为 j 时的最大价值
            data1 = dp[i - 1][j]
            # 放入第 i 个物品时的最大价值，先将背包容量减去第 i 个物品的体积，得到剩余容量 j - num_v[i - 1]
            # 然后加上第 i 个物品的价值 num_w[i - 1]
            data2 = dp[i - 1][j - num_v[i - 1]] + num_w[i - 1]
            # 对不放入和放入第 i 个物品两种情况下的最大价值
            # 更新 dp[i][j] 为这个最大值
            dp[i][j] = max(data1, data2)
# 输出最大价值
print(dp[N][M])



# 定义两个空列表，用于分别存储每个物品的体积和价值
# num_v 列表将存储每个物品的体积
# num_w 列表将存储每个物品对应的价值
num_v = []
num_w = []

# 从用户输入中读取两个整数 N 和 M
# N 表示物品的总数量
# M 表示背包的最大容量
# input().split() 把输入的一行内容按空格分割成多个字符串
# map(int, ...) 将分割后的字符串转换为整数
# 最后将这两个整数分别赋值给变量 N 和 M
N, M = map(int, input().split())

# 通过循环遍历每个物品，获取其体积和价值
# 循环从 0 到 N - 1，共执行 N 次，对应 N 个物品
for i in range(N):
    # 每次循环中，从用户输入读取两个整数 v 和 w
    # v 表示当前物品的体积
    # w 表示当前物品的价值
    v, w = map(int, input().split())
    # 将当前物品的体积 v 添加到 num_v 列表中
    num_v.append(v)
    # 将当前物品的价值 w 添加到 num_w 列表中
    num_w.append(w)

# 创建一个二维列表 dp 用于动态规划
# dp[i][j] 表示前 i 个物品在背包容量为 j 时能获得的最大价值
# 列表的行数为 N + 1，列数为 M + 1，初始值都为 0
# 这里多创建一行一列是为了方便处理边界情况，例如当没有物品（i = 0）或背包容量为 0（j = 0）时
dp = [[0] * (M + 1) for i in range(N + 1)]

# 开始填充 dp 数组，外层循环遍历每个物品
# 从第 1 个物品开始，到第 N 个物品结束
for i in range(1, N + 1):
    # 内层循环遍历背包的不同容量
    # 从背包容量为 1 开始，到最大容量 M 结束
    for j in range(1, M + 1):
        # 判断当前背包容量 j 是否小于第 i 个物品的体积 num_v[i - 1]
        # 注意这里物品的索引是从 0 开始的，所以第 i 个物品在 num_v 和 num_w 列表中的索引是 i - 1
        if j < num_v[i - 1]:
            # 如果当前背包容量不足以放入第 i 个物品
            # 那么前 i 个物品在背包容量为 j 时能获得的最大价值就等于前 i - 1 个物品在相同容量下的最大价值
            dp[i][j] = dp[i - 1][j]
        else:
            # 计算不放入第 i 个物品时的最大价值
            # 即前 i - 1 个物品在背包容量为 j 时的最大价值
            data1 = dp[i - 1][j]
            # 计算放入第 i 个物品时的最大价值
            # 先将背包容量减去第 i 个物品的体积，得到剩余容量 j - num_v[i - 1]
            # 然后加上第 i 个物品的价值 num_w[i - 1]
            data2 = dp[i - 1][j - num_v[i - 1]] + num_w[i - 1]
            # 取不放入和放入第 i 个物品两种情况下的最大价值
            # 更新 dp[i][j] 为这个最大值
            dp[i][j] = max(data1, data2)

# 最终 dp[N][M] 表示前 N 个物品在背包容量为 M 时能获得的最大价值
# 将这个最大价值打印输出
print(dp[N][M])
